Definition

Define the Lagrange dual function g:ℝm×ℝp→ℝg: \mathbb{R}^m \times \mathbb{R}^p \to \mathbb{R} as minimum value of the Lagrangian over xx, i.e. for λ∈ℝm\lambda \in \mathbb{R}^m, ν∈ℝp\nu \in \mathbb{R}^p,

g(λ,ν)=infx∈𝒟⁡L(x,λ,ν)=infx∈𝒟⁡(f0(x)+∑i=1mλifi(x)+∑i=1pνihi(x))g(\lambda, \nu) = \inf_{x \in \mathcal{D}} L(x, \lambda, \nu) = \inf_{x \in \mathcal{D}} \left( f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x) \right)

Notes

  • if Lagrangian is unbounded below in xx, then dual function takes value −∞- \infty.
  • dual function is pointwise infimum of family of affine functions of (λ,ν)(\lambda, \nu), hence concave even when optimization problem is not convex

See also

References

  1. https://en.wikipedia.org/wiki/Duality_(optimization)
  2. S. P. Boyd and L. Vandenberghe, Convex optimization, 2004, p. 216. [Online]. Available: https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf doi: 10.1017/CBO9780511804441 ISBN: 9780521833783